/* poly_mod_2.h
 *
 *	Copyright (C) 2008 CRIMERE
 *	Copyright (C) 2008 Jean-Marc Mercier
 *	
 *	This file is part of OTS (optimally transported schemes), an open-source library
 *	dedicated to scientific computing. http://code.google.com/p/optimally-transported-schemes/
 *
 *	CRIMERE makes no representations about the suitability of this
 *	software for any purpose. It is provided "as is" without express or
 *	implied warranty.
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#ifndef _poly_mod_2_
#define _poly_mod_2_
/*! \file poly_mod_2.h
    \brief Polynomial over Z/2Z with full algebra set of operations. Used for Sobol generators.
*/

#include <boost/operators.hpp>
#include <bitset>
#include <src/miscellaneous/OS_basic.h>

/*! \brief Polynomial over Z/2Z with full algebra set of operations.
    Used for Sobol generators.
*/
template<typename bitset = std::bitset<32> > 
	struct poly_mod_2 : private      
		boost::integer_arithmetic< poly_mod_2 <bitset>          // +, -, *, /, %
	,	boost::totally_ordered < poly_mod_2 <bitset>       // <, ==
	,	boost::bitwise<poly_mod_2 <bitset> >					// ^, |, 
	,	boost::shiftable<poly_mod_2 <bitset>, std::size_t >     // <<, >>
	> >
	, public bitset
{
	typedef typename bitset Base;
	typedef typename bitset bitset;

	poly_mod_2() {};
	poly_mod_2(const std::string & from) : Base(from) {};

	poly_mod_2(unsigned long from) : Base(from){};
	poly_mod_2(const bitset & from) : Base(from){};
	inline poly_mod_2& operator+=(const poly_mod_2 & rhs) {
		*this ^= rhs; 
		return *this;
	};
	inline poly_mod_2& operator-=(const poly_mod_2 & rhs) {
		*this ^= rhs; 
		return *this;
	};
	inline poly_mod_2& operator*=(const poly_mod_2 & rhs) {
		bitset temp = rhs;
		bitset my_temp = *this;
		*this = 0;
		while (temp.to_ulong()) {
			if (temp[0]) {
				*this ^= my_temp; 
			}
			temp >>=1;
			my_temp <<=1;
		};
		return *this;
	};
	inline poly_mod_2& operator/=(const poly_mod_2 & rhs) {

//		1111 - 1100 = 011 - 110 = 11 - 11 = 0
//		x^3+x^2+x+1 = (x+1)*(x2+1) : x^3+x+x^2 +1 OK

		poly_mod_2 temp = rhs;
		poly_mod_2 my_temp = *this;
		*this = 0;
		if (my_temp.degree() > temp.degree())
			temp <<= (my_temp.degree()-temp.degree());
		while (temp.degree()>=rhs.degree()) {
			*(this) <<=1;
			if (my_temp.degree() == temp.degree()) {
					my_temp -= temp;
					(*(this))[0] = 1;
			};
			temp >>= 1;
		};
		return *this;
	};
	inline poly_mod_2& operator%=(const poly_mod_2 & rhs) {
		*this = *this-(*this / rhs)*rhs;  // remainder
		return *this;
	};

	inline poly_mod_2 operator ++(int i) {
		poly_mod_2 temp(*this);
		*this = to_ulong() +1;
		return temp;
	};
	inline poly_mod_2 operator --(int i) {
		poly_mod_2 temp(*this);
		*this = to_ulong() - 1;
		return temp;
	};
	inline poly_mod_2& operator ++() {
		*this = to_ulong() +1;
		return *this;
	};
	inline poly_mod_2& operator --() {
		*this = to_ulong() - 1;
		return *this;
	};
	inline size_t degree() const {
		size_t deg = 0;
		poly_mod_2 temp = *this;
		temp >>= 1;
		while (temp != 0) {
			temp >>=1;
			deg++; }
		return deg;
	};
	inline poly_mod_2& operator~() {
		Base::operator~();
		return *this;
	};
	inline poly_mod_2& operator <<= (std::size_t how) {
		Base::operator <<= (how);
		return *this;
	};
	inline poly_mod_2 operator >>= (std::size_t how) {
		Base::operator >>= (how);
		return *this;
	};
	friend inline OS_bool operator < (const poly_mod_2 &lhs, const poly_mod_2 &rhs) {
		return lhs.to_ulong() < rhs.to_ulong();
	}

	friend inline OS_bool operator == (const poly_mod_2 &lhs, const poly_mod_2 &rhs) {
		return lhs.to_ulong() == rhs.to_ulong();
	}
	friend inline std::ostream& operator<< (std::ostream& o, const poly_mod_2 & t){
		size_t degre = t.degree();
		o << t.to_ulong() << "  (";
		for (size_t i = 0;i <= degre;++i) {
			if (t[i] != 0) {
				if (i!=0) o<<"x^"<<i;
				else o << "1";
				
				if (i!=degre)
					o<<"+";
			};
		};
		o << "  )";
		return o;
	};
};


#endif // _poly_mod_2_

